package arithmetic.alibaba;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 天猫国际每天都会卖出很多跨境商品，用户每次下单可能购买多个商品，购买总数小于10件，由于海关规定，每一个进入海关的箱子里面的商品总额不能超过2000元（否则不能清关）所以当用户下单总金额超过2000，必须使用多个箱子分开包装运输；现在为了节约运输成本，希望在满足海关的要求下，能够使用尽可能少的箱子。 注： 每个商品都有自己的单价，有特定的长宽高，所有商品都是长方体 商品可以横放、竖放、侧放，但不用考虑斜放，但是长宽高各项总和必须都要小于等于箱子的长宽高 假定目前天猫国际使用同一种规格的箱子 boxLong,boxWidth,boxHigh （箱子长，箱子宽，箱子高）
 *
 * 某用户下单买了如下商品 n（商品件数） item1Price,item1Long,item1With,item1High item2Price,item2Long,item2With,item2High item3Price,item3Long,item3With,item3High item4Price,item4Long,item4With,item4High ... （商品价格，商品长，商品宽，商品高） (所有输入类型均为int型正整数)
 *
 * 请你算出需要使用最小的箱子数量，可以将这些商品顺利得清关送到消费者手中，如果无解，输出-1
 *
 * in example: 10 20 30 3 1000 10 10 30 500 10 10 20 600 8 10 20 out example: 2
 */
public class Main {

    /**
     * 一个箱子的商品总额：不超过2000
     */
    public static final int CUSTOMS_LIMIT_MONEY_PER_BOX = 2000;
    BoxTemplate boxTemplate = new BoxTemplate(10, 20, 30, CUSTOMS_LIMIT_MONEY_PER_BOX);

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        Main main = new Main();
        while (true) {
            main.init(scanner);
        }
    }

    public void init(Scanner scanner) {
//			System.out.println("请输入箱子的长宽高：");
//			boxTemplate.length = scanner.nextInt();
//			boxTemplate.width = scanner.nextInt();
//			boxTemplate.height = scanner.nextInt();
        System.out.println("您输入的箱子长宽高为：" + boxTemplate.length + "," + boxTemplate.width + "," + boxTemplate.height);
        System.out.println("请输入商品个数：");
        int itemNum = scanner.nextInt();
        List<Model> items = new ArrayList<Model>();
        for (int i = 0; i < itemNum; i++) {
            System.out.println("请输入第" + (i + 1) + "个商品的价格和长宽高：");
            Model item = new Model(scanner.nextInt(), scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
            items.add(item);
        }
        System.out.println("开始计算：");
        long startTime = System.currentTimeMillis();
        // 结果：用到的最小箱子数，先给初始值-物品个数

        int boxMinNum = -1;
        for (int i = 0; i < items.size(); i++) {
            if (!canInbox(items.get(i))) {
                System.out.print("最小箱子数为：");
                System.out.println(boxMinNum);
                return;
            }
        }
        boxMinNum = itemNum;
        List<Model> result = calculate(items);
        while (boxMinNum > result.size()) {
            boxMinNum = result.size();
            result = calculate(result);
        }
        System.out.print("最小箱子数为：");
        System.out.println(boxMinNum);
        System.out.print("用时：");
        System.out.println(System.currentTimeMillis() - startTime);
    }

    /**
     * 核心计算：给定初始的商品列表和箱子进行合并
     */
    public List<Model> calculate(List<Model> initialModels) {
        if (initialModels.size() < 2) {
            return initialModels;
        }
        List<Model> result = new ArrayList<Model>();
        result.addAll(initialModels);
        for (int i = 0; i < initialModels.size(); i++) {
            for (int j = i + 1; j < initialModels.size(); j++) {
                Model combindedModel = isCanCombined(initialModels.get(i), initialModels.get(j));
                if (null != combindedModel) {
                    result.add(combindedModel);
                    result.remove(initialModels.get(i));
                    result.remove(initialModels.get(j));
                    return result;
                }
            }
        }
        return initialModels;
    }

    /**
     * 给定两个物品和箱子尺寸，判断是否可以合并
     *
     * @return 若可以合并则返回新的尺寸，不能合并则返回null
     */
    public Model isCanCombined(Model a, Model b) {
        Model combinedModel = new Model(a.price + b.price, a.length + b.length, a.width + b.width, a.height + b.height);
        if (canInbox(combinedModel)) {
            return combinedModel;
        }
        return null;
    }

    private boolean canInbox(Model item) {
        return (item.price <= boxTemplate.price &&
            item.length <= boxTemplate.length &&
            item.width <= boxTemplate.width &&
            item.height <= boxTemplate.height);
    }

    /**
     * 箱子的尺寸
     */
    public class BoxTemplate {

        public BoxTemplate(int length, int width, int height, double price) {
            this.length = length;
            this.width = width;
            this.height = height;
            this.price = price;
        }

        public BoxTemplate() {
        }

        int length;
        int width;
        int height;
        double price;
    }

    /**
     * 一个物品的长宽高
     */
    public class Model {

        double price;
        int length;
        int width;
        int height;

        public Model() {
        }

        ;

        public Model(double price, int length, int width, int height) {
            this.price = price;
            this.length = length;
            this.width = width;
            this.height = height;
        }
    }

}